
//version1 : 朴素版本(适用于存储字符只有26个小写英文字母的)
class Trie
{
    struct TrieNode
    {
        int pass = 0;
        int end = 0;
        TrieNode* nexts[26] = {nullptr};//别忘记初始化啊
    };
public:
    Trie()
    {
        root = new TrieNode;
    }
    void insert(string word)
    {
        TrieNode* cur = root;
        cur->pass++;//所有的单词都是以空字符为开头的，所以根节点的pass要++
        for(int i = 0; i < word.size(); i++)//遍历word的每个字母
        {
            char letter = word[i];
            if(cur->nexts[letter - 'a'] == nullptr) cur->nexts[letter - 'a'] = new TrieNode;
            cur = cur->nexts[letter - 'a'];
            cur->pass++;    
        }
        cur->end++;
    }
    bool search(string word) 
    {
        TrieNode* cur = root;
        for(int i = 0; i < word.size(); i++)
        {
            char letter = word[i];
            cur = cur->nexts[letter - 'a'];
            if(cur == nullptr) return false;
        }
        return cur->end > 0;//存在树中存储abcd，但搜索的单词是abc，这种情况abc是不存在的
    }
    bool startsWith(string prefix) 
    {
        TrieNode* cur = root;
        for(int i = 0; i < prefix.size(); i++)
        {
            char letter = prefix[i];
            cur = cur->nexts[letter - 'a'];
            if(cur == nullptr) return false;
        }
        return cur->pass > 0;
    }
    void erase(string word)
    {
        if(search(word))//若单词存在，则删除单词一次
        {
            TrieNode* cur = root;
            cur->pass--;//所有单词都以空字符开头
            for(int i = 0; i < word.size(); i++)
            {
                char letter = word[i];
                if(--cur->nexts[letter - 'a']->pass == 0)
                {
                    Delete(cur->nexts[letter - 'a']);
                    cur->nexts[letter - 'a'] = nullptr;//防止野指针
                    return;
                }
                cur = cur->nexts[letter - 'a'];
            }
            //走出循环，说明该单词整体作为前缀的出现次数大于1，最后多加一步--end，消除该单词的操作即可
            //eg. 前缀树: abc abcd abce abcf 删除单词: abc ，则c字母结点的end需要多减1，直到变为0
            cur->end--;
        }
    }
    void Delete(TrieNode* pos)
    {
        for(int i = 0; i < 26; i++)
        {
            if(pos->nexts[i] != nullptr) 
            {
                Delete(pos->nexts[i]);
                break;
            }
        }
        delete pos;
    }
private:
    TrieNode* root;
};

//version2 : 哈希版本(可适用于存储字符种类理论上无限多种)
class Trie
{
    struct TrieNode
    {
        int pass = 0;
        int end = 0;
        unordered_map<char, TrieNode*> nexts;
    };
public:
    Trie()
    {
        root = new TrieNode;
    }
    void insert(string word)
    {
        TrieNode* cur = root;
        cur->pass++;//所有的单词都是以空字符为开头的，所以根节点的pass要++
        for(int i = 0; i < word.size(); i++)//遍历word的每个字母
        {
            char letter = word[i];
            if(cur->nexts.count(letter) <= 0) cur->nexts[letter] = new TrieNode;
            cur = cur->nexts[letter];
            cur->pass++;
        }
        cur->end++;
    }
    bool search(string word) 
    {
        TrieNode* cur = root;
        for(int i = 0; i < word.size(); i++)
        {
            char letter = word[i];
            if(cur->nexts.count(letter) <= 0) return false;
            cur = cur->nexts[letter];
        }
        return cur->end > 0;//存在树中存储abcd，但搜索的单词是abc，这种情况abc是不存在的
    }
    bool startsWith(string prefix) 
    {
        TrieNode* cur = root;
        for(int i = 0; i < prefix.size(); i++)
        {
            char letter = prefix[i];
            if(cur->nexts.count(letter) <= 0) return false;
            cur = cur->nexts[letter];
        }
        return cur->pass > 0;
    }
    void erase(string word)
    {
        if(search(word))//若单词存在，则删除单词一次
        {
            TrieNode* cur = root;
            cur->pass--;//所有单词都以空字符开头
            for(int i = 0; i < word.size(); i++)
            {
                char letter = word[i];
                if(--cur->nexts[letter]->pass == 0)
                {
                    Delete(cur->nexts[letter]);
                    cur->nexts.erase(letter);
                    return;
                }
                cur = cur->nexts[letter];
            }
            //走出循环，说明该单词整体作为前缀的出现次数大于1，最后多加一步--end，消除该单词的操作即可
            //eg. 前缀树: abc abcd abce abcf 删除单词: abc ，则c字母结点的end需要多减1，直到变为0
            cur->end--;
        }
    }
    void Delete(TrieNode* pos)
    {
        if(pos->nexts.size() == 0) delete pos;
        for(auto [ch, ptr] : pos->nexts)
        {
            Delete(ptr);
            break;
        }
        delete pos;
    }
private:
    TrieNode* root;
};